package com.fyl.leetcode.BFS;

import com.fyl.basic_algorithm.backtrack.Queens;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Queue;

/**
 * @author:fyl
 * @date 2021/5/15 11:19
 * @Modified By:
 * @Modified Date:
 * @Description: 给定正整数n，找到若干个完全平方数（比如1, 4, 9, 16, ...）使得它们的和等于 n。你需要让组成和的完全平方数的个数最少。
 * 给你一个整数 n ，返回和为 n 的完全平方数的 最少数量 。
 * 完全平方数 是一个整数，其值等于另一个整数的平方；换句话说，其值等于一个整数自乘的积。例如，1、4、9 和 16 都是完全平方数，而 3 和 11 不是。
 */
public class NumSquares {

    //可以将每个整数看成图中的一个节点，如果两个整数之差为一个平方数，那么这两个整数所在的节点就有一条边。
    //要求解最小的平方数数量，就是求解从节点 n 到节点 0 的最短路径。
    public static int numSquares(int n) {
        ArrayList<Integer> squareNums = new ArrayList<Integer>();
        for (int i = 1; i * i <= n; ++i) {
            squareNums.add(i * i);
        }
        Queue<Integer> queue = new LinkedList<Integer>();
        boolean[] marked = new boolean[n + 1];
        queue.add(n);
        marked[n] = true;
        int level = 0;
        while (!queue.isEmpty()) {
            int size = queue.size();
            level++;
            while (size-- > 0) {
                Integer cur = queue.poll();
                for (Integer num : squareNums) {
                    int next = cur - num;
                    if (next < 0) {
                        break;
                    }
                    if (next == 0) {
                        return level;
                    }
                    if (marked[next]) {
                        continue;
                    }
                    marked[next] = true;
                    queue.add(next);
                }
            }
        }
        return n;
    }

    //动态规划
//    public static int numSquares(int n) {
//        int db[] = new int[n + 1];
//        Arrays.fill(db, Integer.MAX_VALUE);
//        db[0] = 0;
//        //最大的平方数
//        int max_square_index = (int) Math.sqrt(n) + 1;
//        //预计算小于给定数字 n 的完全平方数列表
//        int square_nums[] = new int[max_square_index];
//        for (int i = 1; i < max_square_index; ++i) {
//            square_nums[i] = i * i;
//        }
//
//        //我们从数字 1 循环到 n，计算每个数字 i 的解（即 numSquares(i)）。
//        // 每次迭代中，我们将 numSquares(i) 的结果保存在 dp[i] 中。
//        //求解公式 numSquares(n)=min(numSquares(n-k) + 1)∀k∈square numbers
//        for (int i = 1; i <= n; ++i) {
//            for (int j = 1; j < max_square_index; ++j) {
//                //防止数组下标越界
//                if (i < square_nums[j])
//                    break;
//                db[i] = Math.min(db[i], db[i - square_nums[j]] + 1);
//            }
//        }
//        return db[n];
//    }

    public static void main(String[] args) {
        System.out.println(numSquares(12));
    }
}
